package interview;
//面试题 02.04. 分割链表
public class Num02_04_partition {
    public ListNode partition(ListNode head, int x) {
        //边界
        if (head==null){
            return null;
        }
        ListNode smallHead = new ListNode(101);
        ListNode smallTail = smallHead;
        ListNode bigHead = new ListNode(101);
        ListNode bigTail = bigHead;
        //遍历原链表
        while (head != null) {
            if (head.val < x) {
                // 尾插入小链表
                smallTail.next = head;
                smallTail = head;
            }else {
                bigTail.next = head;
                bigTail = head;
            }
            head = head.next;
        }
        // 拼接大小链表
        bigTail.next = null;
        smallTail.next = bigHead.next;
        return smallHead.next;





    }

}
